This invention relates generally to digital signal processing circuits, and, more particularly, to circuitry for performing a fast Fourier transform (FFT) function on a set of data input signals. Fourier transformation is a mathematical algorithm for deriving a frequency spectrum of a time-varying quantity, usually in the form of an electrical signal. Fourier transforms are useful in a wide variety of applications involving spectrum analysis.
Some preliminary definitions will serve to provide a basis for further discussion of Fourier transforms. First, a graph plotting the variation of a signal value with respect to time is referred to as a representation of the signal in the time domain. A corresponding plot of the spectral content of the signal, showing signal amplitudes for a range of frequencies, is referred to as a representation of the signal in the frequency domain. The Fourier transform is a mathematical formula for converting a signal from a time-domain representation to a frequency-domain representation. The inverse Fourier transform is a formula for converting a signal from a frequency-domain representation to a time-domain representation. The discrete Fourier transform (DFT) may be viewed as a special case of the continuous form of the Fourier transform. The DFT determines a set of spectrum amplitudes or coefficients from a time-varying signal defined by a periodic sequence of samples taken at discrete time intervals.
As is well known, in the mid-1960's techniques were developed for more rapid computation of the discrete Fourier transform. These techniques became known as the fast Fourier transform (FFT), first described in a paper by J. W. Cooley and J. W. Tukey, entitled "An Algorithm for the Machine Calculation of Complex Fourier Series," Mathematics of Computation (1965), Vol. 19, No. 90, pp. 297-301.
Since the development of the fast Fourier transform, many different designs have been proposed for hardware implementation of the discrete Fourier transform. U.S. Pat. No. 4,156,920, issued in the name of Winograd and entitled "Computer System Architecture for Performing Nested Loop Operations to Effect a Discrete Fourier Transform," lists a number of patents in the field. The Winograd patent and the patents listed therein at Column 4 were believed to the exemplary of the prior art. Basically, prior inventions in this area have focused on a variety of special architectures for simplifying or improving the efficiency of calculations of the Fourier transform. Prior to this invention, however, such specially designed FFT hardware has been relatively bulky and inefficient, with respect to both speed and power consumption. Furthermore, the organization of such hardware has in the past involved the use of a few fast computation elements sharing a common memory. In such systems, computation rates are typically limited by memory access time and are relatively slow.
Since the development of microprocessors, an increasingly common technique for computing the fast Fourier transform is to employ a microprocessor programmed to perform the function. Again, however, because of the generalized nature of microprocessor architecture, the relatively slow speed of computation is a significant limiting factor for many applications. Another problem with prior-art FFT hardware, whether of special-purpose design or based on a microprocessor implementation, is that these designs are not easily expandable to handle large FFT computations at high speed and without bulky circuitry.
In view of the foregoing, it will be apparent that there has until now been a significant need for improvement in fast Fourier transform circuits. In particular, there has been a special need for a fast Fourier transform circuit having low power consumption, small size, very high speed, and the ability to be expanded to accommodate relatively large FFT computations. The present invention fulfills this need.